package com.vic.geektime.math.chapter05;

import java.util.ArrayList;

/**
 *  @title Lesson5_append1
 *  @Description <p>一个整数可以被分解为多个整数的乘积，例如，6 可以分解为 2x3。
 *  请使用递归编程的方法，为给定的整数 n，找到所有可能的分解（1 在解中最多只能出现 1 次）。
 *  例如，输入 8，输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2x2, 1x2x4, ……</p>
 *  @author Karson Wang
 *  @Date 2020/3/27 20:16
 *  @Copyright 2019-2020
 */
public class Lesson5_append1 {

    public static void recursion(long total, ArrayList<Long> result) {

        if (total == 1) {
            if (!result.contains(1L)) result.add(1L);
            System.out.println(result);
            return;
        } else {
            for (long i = 1; i <= total; i++) {
                // 已经包含1则继续
                if ((i == 1) && result.contains(1L)) continue;
                // 不能整除跳过
                if (total % i != 0) {
                    continue;
                }
                ArrayList<Long> newList = (ArrayList<Long>) (result.clone());
                newList.add(Long.valueOf(i));

                recursion(total / i, newList);
            }
        }
    }

    public static void main(String[] args) {
        recursion(8, new ArrayList<Long>());
    }
}
